A file is a kind of dynamically-allocated data structure that an application program can access by name. The application program reads or writes to the file by sending a read or write request to an operating system program called a file system manager. The read or write request specifies the file, an offset in a logical extent of the file, and a number of blocks of data to be read or written, beginning at the specified offset. The typical size of one block of data is four kilobytes or eight kilobytes.
The file system manager maintains the file in a collection of files called a file system. The file system is built upon a logical volume of file system blocks. To an application program, the file system appears to be a tree of directories, subdirectories, and files. The file system manager maintains additional data structures in the file system, such as a map of the file system blocks that are free and the file system blocks that have been allocated to files in the file system.
Popular file systems permit any free block of the file system to be allocated to a file of the file system and mapped to any logical block of the logical extent of the file. The additional flexibility of file system block allocation permits more efficient storage utilization by reducing storage fragmentation and permitting sparse files and efficient dynamic extension of files.
For example, one very popular file system is known as the UNIX-based file system. The UNIX-based file system is described in Uresh Vahalia, Unix Internals—The New Frontiers, Chapter 9, File System Implementations, pp. 261-290, Prentice-Hall, Inc., Upper Saddle River, N.J. (1996). The file in the UNIX-based file system is a hierarchy of file system blocks. The file system block at the top or root of the hierarchy is called an “inode.” The inode contains attributes of the file and also a block pointer array including pointers to one or more file system blocks that are directly below the inode in the hierarchy. The data of the file is contained in one or more file system data blocks at the bottom or leaves of the hierarchy. If the file contains more than ten data blocks, then there will be at least one indirect block directly below inode in the hierarchy. Each indirect block includes a block pointer array of up to 256 block pointers.
The popular file systems that permit flexible block mapping in the files suffer a file fragmentation problem when large files are accessed randomly over time. File fragmentation is most noticeable as a gradual decrease in read performance. A file is fragmented when the logical extent of the file is not mapped to a single extent of contiguous file system blocks in the logical volume of the file system. If the logical extent of a file becomes mapped to a large number of relatively small extents that are widely distributed over the logical volume of the file system, then this fragmentation of the data storage of the file causes the performance of file access to suffer from an inability to obtain locality of access to the data storage. Locality of access is desired because it increases the likelihood that address translation caches and data caches in the digital computer will contain the addresses and data for access to the file. Locality of access also improves the fetching and streaming of data from the data storage.
A known method of dealing with file fragmentation is to run a background defragmentation process in order to restore read performance upon large files. The background defragmentation process, however, contends with user I/O for locks and file mapping metadata, so that the defragmentation process should be designed and operated with care so as to be transparent to application programs. See, for example, the storage reorganizer described in Bono et al., U.S. Pat. No. 7,631,155 issued Dec. 8, 2009, entitled Thin Provisioning of a File System and an ISCSI LUN Through a Common Mechanism.